
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <limits.h>
#include <sys/time.h>
#include <ctype.h>

#include "appnet_dict.h"
#include "zmalloc.h"
#include <assert.h>

/* Using dictEnableResize() / dictDisableResize() we make possible to
 * enable/disable resizing of the hash table as needed. This is very important
 * for Redis, as we use copy-on-write and don't want to move too much memory
 * around when there is a child performing saving operations.
 *
 * Note that even when dict_can_resize is set to 0, not all resizes are
 * prevented: a hash table is still allowed to grow if the ratio between
 * the number of elements and the buckets > dict_force_resize_ratio. */
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

/* -------------------------- private prototypes ---------------------------- */

static int _dictExpandIfNeeded( dict *ht );
static unsigned long _dictNextPower( unsigned long size );
static int _dictKeyIndex( dict *ht , const void *key );
static int _dictInit( dict *ht , dictType *type , void *privDataPtr );

/* -------------------------- hash functions -------------------------------- */

/* Thomas Wang's 32 bit Mix Function */
unsigned int dictIntHashFunction( unsigned int key )
{
	key += ~( key << 15 );
	key ^= ( key >> 10 );
	key += ( key << 3 );
	key ^= ( key >> 6 );
	key += ~( key << 11 );
	key ^= ( key >> 16 );
	return key;
}

static uint32_t dict_hash_function_seed = 5381;

void dictSetHashFunctionSeed( uint32_t seed )
{
	dict_hash_function_seed = seed;
}

uint32_t dictGetHashFunctionSeed( void )
{
	return dict_hash_function_seed;
}

/* MurmurHash2, by Austin Appleby
 * Note - This code makes a few assumptions about how your machine behaves -
 * 1. We can read a 4-byte value from any address without crashing
 * 2. sizeof(int) == 4
 *
 * And it has a few limitations -
 *
 * 1. It will not work incrementally.
 * 2. It will not produce the same results on little-endian and big-endian
 *    machines.
 */
unsigned int dictGenHashFunction( const void *key , int len )
{
	/* 'm' and 'r' are mixing constants generated offline.
	 They're not really 'magic', they just happen to work well.  */
	uint32_t seed = dict_hash_function_seed;
	const uint32_t m = 0x5bd1e995;
	const int r = 24;
	/* Initialize the hash to a 'random' value */
	uint32_t h = seed ^ len;
	/* Mix 4 bytes at a time into the hash */
	const unsigned char *data = (const unsigned char *) key;
	while (len >= 4)
	{
		uint32_t k = *(uint32_t*) data;
		k *= m;
		k ^= k >> r;
		k *= m;
		h *= m;
		h ^= k;
		data += 4;
		len -= 4;
	}
	/* Handle the last few bytes of the input array  */
	switch (len)
	{
		case 3:
			h ^= data[2] << 16;
		case 2:
			h ^= data[1] << 8;
		case 1:
			h ^= data[0];
			h *= m;
	};
	/* Do a few final mixes of the hash to ensure the last few
	 * bytes are well-incorporated. */
	h ^= h >> 13;
	h *= m;
	h ^= h >> 15;
	return (unsigned int) h;
}

/* And a case insensitive hash function (based on djb hash) */
unsigned int dictGenCaseHashFunction( const unsigned char *buf , int len )
{
	unsigned int hash = (unsigned int) dict_hash_function_seed;
	while (len--)
	{
		hash = ( ( hash << 5 ) + hash ) + ( tolower( *buf++ ) ); /* hash * 33 + c */
	}
	return hash;
}

/* ----------------------------- API implementation ------------------------- */

/* Reset a hash table already initialized with ht_init().
 * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset( dictht *ht )
{
	ht->table = NULL;
	ht->size = 0;
	ht->sizemask = 0;
	ht->used = 0;
}

/* Create a new hash table */
dict *dictCreate( dictType *type ,
		void *privDataPtr )
{
	dict *d = zmalloc( sizeof( *d ) );
	_dictInit( d , type , privDataPtr );
	return d;
}

/* Initialize the hash table */
int _dictInit( dict *d , dictType *type ,
		void *privDataPtr )
{
	_dictReset( &d->ht[0] );
	_dictReset( &d->ht[1] );
	d->type = type;
	d->privdata = privDataPtr;
	d->rehashidx = -1;
	d->iterators = 0;
	return DICT_OK;
}

/* Resize the table to the minimal size that contains all the elements,
 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize( dict *d )
{
	int minimal;
	if (!dict_can_resize || dictIsRehashing(d) )
	{
		return DICT_ERR;
	}
	minimal = d->ht[0].used;
	if (minimal < DICT_HT_INITIAL_SIZE)
	{
		minimal = DICT_HT_INITIAL_SIZE;
	}
	return dictExpand( d , minimal );
}

/* Expand or create the hash table */
int dictExpand( dict *d , unsigned long size )
{
	dictht n; /* the new hash table */
	unsigned long realsize = _dictNextPower( size );
	/* the size is invalid if it is smaller than the number of
	 * elements already inside the hash table */
	if (dictIsRehashing(d) || d->ht[0].used > size)
	{
		return DICT_ERR;
	}
	/* Rehashing to the same table size is not useful. */
	if (realsize == d->ht[0].size)
	{
		return DICT_ERR;
	}
	/* Allocate the new hash table and initialize all pointers to NULL */
	n.size = realsize;
	n.sizemask = realsize - 1;
	n.table = zcalloc( realsize * sizeof(dictEntry*) );
	n.used = 0;
	/* Is this the first initialization? If so it's not really a rehashing
	 * we just set the first hash table so that it can accept keys. */
	if (d->ht[0].table == NULL)
	{
		d->ht[0] = n;
		return DICT_OK;
	}
	/* Prepare a second hash table for incremental rehashing */
	d->ht[1] = n;
	d->rehashidx = 0;
	return DICT_OK;
}

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash( dict *d , int n )
{
	int empty_visits = n * 10; /* Max number of empty buckets to visit. */
	if (!dictIsRehashing(d) )
	{
		return 0;
	}
	while (n-- && d->ht[0].used != 0)
	{
		dictEntry *de,*nextde;
		/* Note that rehashidx can't overflow as we are sure there are more
		 * elements because ht[0].used != 0 */
		assert( d->ht[0].size > (unsigned long) d->rehashidx );
		while (d->ht[0].table[d->rehashidx] == NULL)
		{
			d->rehashidx++;
			if (--empty_visits == 0)
			{
				return 1;
			}
		}
		de = d->ht[0].table[d->rehashidx];
		/* Move all the keys in this bucket from the old to the new hash HT */
		while (de)
		{
			unsigned int h;
			nextde = de->next;
			/* Get the index in the new hash table */
			h = dictHashKey(d, de->key) & d->ht[1].sizemask;
			de->next = d->ht[1].table[h];
			d->ht[1].table[h] = de;
			d->ht[0].used--;
			d->ht[1].used++;
			de = nextde;
		}
		d->ht[0].table[d->rehashidx] = NULL;
		d->rehashidx++;
	}
	/* Check if we already rehashed the whole table... */
	if (d->ht[0].used == 0)
	{
		zfree( d->ht[0].table );
		d->ht[0] = d->ht[1];
		_dictReset( &d->ht[1] );
		d->rehashidx = -1;
		return 0;
	}
	/* More to rehash... */
	return 1;
}

long long timeInMilliseconds( void )
{
	struct timeval tv;
	gettimeofday( &tv , NULL );
	return ( ( (long long) tv.tv_sec ) * 1000 ) + ( tv.tv_usec / 1000 );
}

/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
int dictRehashMilliseconds( dict *d , int ms )
{
	long long start = timeInMilliseconds();
	int rehashes = 0;
	while (dictRehash( d , 100 ))
	{
		rehashes += 100;
		if (timeInMilliseconds() - start > ms)
		{
			break;
		}
	}
	return rehashes;
}

/* This function performs just a step of rehashing, and only if there are
 * no safe iterators bound to our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
static void _dictRehashStep( dict *d )
{
	if (d->iterators == 0)
	{
		dictRehash( d , 1 );
	}
}

/* Add an element to the target hash table */
int dictAdd( dict *d , void *key , void *val )
{
	dictEntry *entry = dictAddRaw( d , key );
	if (!entry)
	{
		return DICT_ERR;
	}
	dictSetVal( d , entry , val );
	return DICT_OK;
}

/* Low level add. This function adds the entry but instead of setting
 * a value returns the dictEntry structure to the user, that will make
 * sure to fill the value field as he wishes.
 *
 * This function is also directly exposed to the user API to be called
 * mainly in order to store non-pointers inside the hash value, example:
 *
 * entry = dictAddRaw(dict,mykey);
 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 * Return values:
 *
 * If key already exists NULL is returned.
 * If key was added, the hash entry is returned to be manipulated by the caller.
 */
dictEntry *dictAddRaw( dict *d , void *key )
{
	int index;
	dictEntry *entry;
	dictht *ht;
	if (dictIsRehashing(d) )
	{
		_dictRehashStep( d );
	}
	/* Get the index of the new element, or -1 if
	 * the element already exists. */
	if (( index = _dictKeyIndex( d , key ) ) == -1)
	{
		return NULL;
	}
	/* Allocate the memory and store the new entry */
	ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
	entry = zmalloc( sizeof( *entry ) );
	entry->next = ht->table[index];
	ht->table[index] = entry;
	ht->used++;
	/* Set the hash entry fields. */
	dictSetKey( d , entry , key );
	return entry;
}

/* Add an element, discarding the old if the key already exists.
 * Return 1 if the key was added from scratch, 0 if there was already an
 * element with such key and dictReplace() just performed a value update
 * operation. */
int dictReplace( dict *d , void *key , void *val )
{
	dictEntry *entry,auxentry;
	/* Try to add the element. If the key
	 * does not exists dictAdd will suceed. */
	if (dictAdd( d , key , val ) == DICT_OK)
	{
		return 1;
	}
	/* It already exists, get the entry */
	entry = dictFind( d , key );
	/* Set the new value and free the old one. Note that it is important
	 * to do that in this order, as the value may just be exactly the same
	 * as the previous one. In this context, think to reference counting,
	 * you want to increment (set), and then decrement (free), and not the
	 * reverse. */
	auxentry = *entry;
	dictSetVal( d , entry , val );
	dictFreeVal( d , &auxentry );
	return 0;
}

/* dictReplaceRaw() is simply a version of dictAddRaw() that always
 * returns the hash entry of the specified key, even if the key already
 * exists and can't be added (in that case the entry of the already
 * existing key is returned.)
 *
 * See dictAddRaw() for more information. */
dictEntry *dictReplaceRaw( dict *d , void *key )
{
	dictEntry *entry = dictFind( d , key );
	return entry ? entry : dictAddRaw( d , key );
}

/* Search and remove an element */
static int dictGenericDelete( dict *d , const void *key , int nofree )
{
	unsigned int h,idx;
	dictEntry *he,*prevHe;
	int table;
	if (d->ht[0].size == 0)
	{
		return DICT_ERR; /* d->ht[0].table is NULL */
	}
	if (dictIsRehashing(d) )
	{
		_dictRehashStep( d );
	}
	h = dictHashKey(d, key);
	for (table = 0; table <= 1; table++)
	{
		idx = h & d->ht[table].sizemask;
		he = d->ht[table].table[idx];
		prevHe = NULL;
		while (he)
		{
			if (dictCompareKeys(d, key, he->key) )
					{
				/* Unlink the element from the list */
				if (prevHe)
				{
					prevHe->next = he->next;
				}
				else
				{
					d->ht[table].table[idx] = he->next;
				}
				if (!nofree)
				{
					dictFreeKey( d , he );
					dictFreeVal( d , he );
				}
				zfree( he );
				d->ht[table].used--;
				return DICT_OK;
			}
			prevHe = he;
			he = he->next;
		}
		if (!dictIsRehashing(d) )
		{
			break;
		}
	}
	return DICT_ERR; /* not found */
}

int dictDelete( dict *ht , const void *key )
{
	return dictGenericDelete( ht , key , 0 );
}

int dictDeleteNoFree( dict *ht , const void *key )
{
	return dictGenericDelete( ht , key , 1 );
}

/* Destroy an entire dictionary */
int _dictClear( dict *d , dictht *ht , void (callback)( void * ) )
{
	unsigned long i;
	/* Free all the elements */
	for (i = 0; i < ht->size && ht->used > 0; i++)
	{
		dictEntry *he,*nextHe;
		if (callback && ( i & 65535 ) == 0)
		{
			callback( d->privdata );
		}
		if (( he = ht->table[i] ) == NULL)
		{
			continue;
		}
		while (he)
		{
			nextHe = he->next;
			dictFreeKey( d , he );
			dictFreeVal( d , he );
			zfree( he );
			ht->used--;
			he = nextHe;
		}
	}
	/* Free the table and the allocated cache structure */
	zfree( ht->table );
	/* Re-initialize the table */
	_dictReset( ht );
	return DICT_OK; /* never fails */
}

/* Clear & Release the hash table */
void dictRelease( dict *d )
{
	_dictClear( d , &d->ht[0] , NULL );
	_dictClear( d , &d->ht[1] , NULL );
	zfree( d );
}

dictEntry *dictFind( dict *d , const void *key )
{
	dictEntry *he;
	unsigned int h,idx,table;
	if (d->ht[0].size == 0)
	{
		return NULL; /* We don't have a table at all */
	}
	if (dictIsRehashing(d) )
	{
		_dictRehashStep( d );
	}
	h = dictHashKey(d, key);
	for (table = 0; table <= 1; table++)
	{
		idx = h & d->ht[table].sizemask;
		he = d->ht[table].table[idx];
		while (he)
		{
			if (dictCompareKeys(d, key, he->key) )
					{
				return he;
			}
			he = he->next;
		}
		if (!dictIsRehashing(d) )
		{
			return NULL;
		}
	}
	return NULL;
}

void *dictFetchValue( dict *d , const void *key )
{
	dictEntry *he;
	he = dictFind( d , key );
	return he ? dictGetVal(he) : NULL;
}

/* A fingerprint is a 64 bit number that represents the state of the dictionary
 * at a given time, it's just a few dict properties xored together.
 * When an unsafe iterator is initialized, we get the dict fingerprint, and check
 * the fingerprint again when the iterator is released.
 * If the two fingerprints are different it means that the user of the iterator
 * performed forbidden operations against the dictionary while iterating. */
long long dictFingerprint( dict *d )
{
	long long integers[6],hash = 0;
	int j;
	integers[0] = (long) d->ht[0].table;
	integers[1] = d->ht[0].size;
	integers[2] = d->ht[0].used;
	integers[3] = (long) d->ht[1].table;
	integers[4] = d->ht[1].size;
	integers[5] = d->ht[1].used;
	/* We hash N integers by summing every successive integer with the integer
	 * hashing of the previous sum. Basically:
	 *
	 * Result = hash(hash(hash(int1)+int2)+int3) ...
	 *
	 * This way the same set of integers in a different order will (likely) hash
	 * to a different number. */
	for (j = 0; j < 6; j++)
	{
		hash += integers[j];
		/* For the hashing step we use Tomas Wang's 64 bit integer hash. */
		hash = ( ~hash ) + ( hash << 21 ); // hash = (hash << 21) - hash - 1;
		hash = hash ^ ( hash >> 24 );
		hash = ( hash + ( hash << 3 ) ) + ( hash << 8 ); // hash * 265
		hash = hash ^ ( hash >> 14 );
		hash = ( hash + ( hash << 2 ) ) + ( hash << 4 ); // hash * 21
		hash = hash ^ ( hash >> 28 );
		hash = hash + ( hash << 31 );
	}
	return hash;
}

dictIterator *dictGetIterator( dict *d )
{
	dictIterator *iter = zmalloc( sizeof( *iter ) );
	iter->d = d;
	iter->table = 0;
	iter->index = -1;
	iter->safe = 0;
	iter->entry = NULL;
	iter->nextEntry = NULL;
	return iter;
}

dictIterator *dictGetSafeIterator( dict *d )
{
	dictIterator *i = dictGetIterator( d );
	i->safe = 1;
	return i;
}

dictEntry *dictNext( dictIterator *iter )
{
	while (1)
	{
		if (iter->entry == NULL)
		{
			dictht *ht = &iter->d->ht[iter->table];
			if (iter->index == -1 && iter->table == 0)
			{
				if (iter->safe)
				{
					iter->d->iterators++;
				}
				else
				{
					iter->fingerprint = dictFingerprint( iter->d );
				}
			}
			iter->index++;
			if (iter->index >= (long) ht->size)
			{
				if (dictIsRehashing(iter->d) && iter->table == 0)
				{
					iter->table++;
					iter->index = 0;
					ht = &iter->d->ht[1];
				}
				else
				{
					break;
				}
			}
			iter->entry = ht->table[iter->index];
		}
		else
		{
			iter->entry = iter->nextEntry;
		}
		if (iter->entry)
		{
			/* We need to save the 'next' here, the iterator user
			 * may delete the entry we are returning. */
			iter->nextEntry = iter->entry->next;
			return iter->entry;
		}
	}
	return NULL;
}

void dictReleaseIterator( dictIterator *iter )
{
	if (!( iter->index == -1 && iter->table == 0 ))
	{
		if (iter->safe)
		{
			iter->d->iterators--;
		}
		else
		{
			assert( iter->fingerprint == dictFingerprint( iter->d ) );
		}
	}
	zfree( iter );
}

/* Return a random entry from the hash table. Useful to
 * implement randomized algorithms */
dictEntry *dictGetRandomKey( dict *d )
{
	dictEntry *he,*orighe;
	unsigned int h;
	int listlen,listele;
	if (dictSize(d) == 0)
	{
		return NULL;
	}
	if (dictIsRehashing(d) )
	{
		_dictRehashStep( d );
	}
	if (dictIsRehashing(d) )
	{
		do
		{
			/* We are sure there are no elements in indexes from 0
			 * to rehashidx-1 */
			h = d->rehashidx + ( random() % ( d->ht[0].size +
					d->ht[1].size -
					d->rehashidx ) );
			he = ( h >= d->ht[0].size ) ? d->ht[1].table[h - d->ht[0].size] :
											d->ht[0].table[h];
		}
		while (he == NULL);
	}
	else
	{
		do
		{
			h = random() & d->ht[0].sizemask;
			he = d->ht[0].table[h];
		}
		while (he == NULL);
	}
	/* Now we found a non empty bucket, but it is a linked
	 * list and we need to get a random element from the list.
	 * The only sane way to do so is counting the elements and
	 * select a random index. */
	listlen = 0;
	orighe = he;
	while (he)
	{
		he = he->next;
		listlen++;
	}
	listele = random() % listlen;
	he = orighe;
	while (listele--)
	{
		he = he->next;
	}
	return he;
}

/* This function samples the dictionary to return a few keys from random
 * locations.
 *
 * It does not guarantee to return all the keys specified in 'count', nor
 * it does guarantee to return non-duplicated elements, however it will make
 * some effort to do both things.
 *
 * Returned pointers to hash table entries are stored into 'des' that
 * points to an array of dictEntry pointers. The array must have room for
 * at least 'count' elements, that is the argument we pass to the function
 * to tell how many random elements we need.
 *
 * The function returns the number of items stored into 'des', that may
 * be less than 'count' if the hash table has less than 'count' elements
 * inside, or if not enough elements were found in a reasonable amount of
 * steps.
 *
 * Note that this function is not suitable when you need a good distribution
 * of the returned items, but only when you need to "sample" a given number
 * of continuous elements to run some kind of algorithm or to produce
 * statistics. However the function is much faster than dictGetRandomKey()
 * at producing N elements. */
unsigned int dictGetSomeKeys( dict *d , dictEntry **des , unsigned int count )
{
	unsigned int j; /* internal hash table id, 0 or 1. */
	unsigned int tables; /* 1 or 2 tables? */
	unsigned int stored = 0,maxsizemask;
	unsigned int maxsteps;
	if (dictSize(d) < count)
	{
		count = dictSize(d);
	}
	maxsteps = count * 10;
	/* Try to do a rehashing work proportional to 'count'. */
	for (j = 0; j < count; j++)
	{
		if (dictIsRehashing(d) )
		{
			_dictRehashStep( d );
		}
		else
		{
			break;
		}
	}
	tables = dictIsRehashing(d) ? 2 : 1;
	maxsizemask = d->ht[0].sizemask;
	if (tables > 1 && maxsizemask < d->ht[1].sizemask)
	{
		maxsizemask = d->ht[1].sizemask;
	}
	/* Pick a random point inside the larger table. */
	unsigned int i = random() & maxsizemask;
	unsigned int emptylen = 0; /* Continuous empty entries so far. */
	while (stored < count && maxsteps--)
	{
		for (j = 0; j < tables; j++)
		{
			/* Invariant of the dict.c rehashing: up to the indexes already
			 * visited in ht[0] during the rehashing, there are no populated
			 * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */
			if (tables == 2 && j == 0 && i < (unsigned int) d->rehashidx)
			{
				/* Moreover, if we are currently out of range in the second
				 * table, there will be no elements in both tables up to
				 * the current rehashing index, so we jump if possible.
				 * (this happens when going from big to small table). */
				if (i >= d->ht[1].size)
				{
					i = d->rehashidx;
				}
				continue;
			}
			if (i >= d->ht[j].size)
			{
				continue; /* Out of range for this table. */
			}
			dictEntry *he = d->ht[j].table[i];
			/* Count contiguous empty buckets, and jump to other
			 * locations if they reach 'count' (with a minimum of 5). */
			if (he == NULL)
			{
				emptylen++;
				if (emptylen >= 5 && emptylen > count)
				{
					i = random() & maxsizemask;
					emptylen = 0;
				}
			}
			else
			{
				emptylen = 0;
				while (he)
				{
					/* Collect all the elements of the buckets found non
					 * empty while iterating. */
					*des = he;
					des++;
					he = he->next;
					stored++;
					if (stored == count)
					{
						return stored;
					}
				}
			}
		}
		i = ( i + 1 ) & maxsizemask;
	}
	return stored;
}

/* Function to reverse bits. Algorithm from:
 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev( unsigned long v )
{
	unsigned long s = 8 * sizeof( v ); // bit size; must be power of 2
	unsigned long mask = ~0;
	while (( s >>= 1 ) > 0)
	{
		mask ^= ( mask << s );
		v = ( ( v >> s ) & mask ) | ( ( v << s ) & ~mask );
	}
	return v;
}

/* dictScan() is used to iterate over the elements of a dictionary.
 *
 * Iterating works the following way:
 *
 * 1) Initially you call the function using a cursor (v) value of 0.
 * 2) The function performs one step of the iteration, and returns the
 *    new cursor value you must use in the next call.
 * 3) When the returned cursor is 0, the iteration is complete.
 *
 * The function guarantees all elements present in the
 * dictionary get returned between the start and end of the iteration.
 * However it is possible some elements get returned multiple times.
 *
 * For every element returned, the callback argument 'fn' is
 * called with 'privdata' as first argument and the dictionary entry
 * 'de' as second argument.
 *
 * HOW IT WORKS.
 *
 * The iteration algorithm was designed by Pieter Noordhuis.
 * The main idea is to increment a cursor starting from the higher order
 * bits. That is, instead of incrementing the cursor normally, the bits
 * of the cursor are reversed, then the cursor is incremented, and finally
 * the bits are reversed again.
 *
 * This strategy is needed because the hash table may be resized between
 * iteration calls.
 *
 * dict.c hash tables are always power of two in size, and they
 * use chaining, so the position of an element in a given table is given
 * by computing the bitwise AND between Hash(key) and SIZE-1
 * (where SIZE-1 is always the mask that is equivalent to taking the rest
 *  of the division between the Hash of the key and SIZE).
 *
 * For example if the current hash table size is 16, the mask is
 * (in binary) 1111. The position of a key in the hash table will always be
 * the last four bits of the hash output, and so forth.
 *
 * WHAT HAPPENS IF THE TABLE CHANGES IN SIZE?
 *
 * If the hash table grows, elements can go anywhere in one multiple of
 * the old bucket: for example let's say we already iterated with
 * a 4 bit cursor 1100 (the mask is 1111 because hash table size = 16).
 *
 * If the hash table will be resized to 64 elements, then the new mask will
 * be 111111. The new buckets you obtain by substituting in ??1100
 * with either 0 or 1 can be targeted only by keys we already visited
 * when scanning the bucket 1100 in the smaller hash table.
 *
 * By iterating the higher bits first, because of the inverted counter, the
 * cursor does not need to restart if the table size gets bigger. It will
 * continue iterating using cursors without '1100' at the end, and also
 * without any other combination of the final 4 bits already explored.
 *
 * Similarly when the table size shrinks over time, for example going from
 * 16 to 8, if a combination of the lower three bits (the mask for size 8
 * is 111) were already completely explored, it would not be visited again
 * because we are sure we tried, for example, both 0111 and 1111 (all the
 * variations of the higher bit) so we don't need to test it again.
 *
 * WAIT... YOU HAVE *TWO* TABLES DURING REHASHING!
 *
 * Yes, this is true, but we always iterate the smaller table first, then
 * we test all the expansions of the current cursor into the larger
 * table. For example if the current cursor is 101 and we also have a
 * larger table of size 16, we also test (0)101 and (1)101 inside the larger
 * table. This reduces the problem back to having only one table, where
 * the larger one, if it exists, is just an expansion of the smaller one.
 *
 * LIMITATIONS
 *
 * This iterator is completely stateless, and this is a huge advantage,
 * including no additional memory used.
 *
 * The disadvantages resulting from this design are:
 *
 * 1) It is possible we return elements more than once. However this is usually
 *    easy to deal with in the application level.
 * 2) The iterator must return multiple elements per call, as it needs to always
 *    return all the keys chained in a given bucket, and all the expansions, so
 *    we are sure we don't miss keys moving during rehashing.
 * 3) The reverse cursor is somewhat hard to understand at first, but this
 *    comment is supposed to help.
 */
unsigned long dictScan( dict *d ,
		unsigned long v ,
		dictScanFunction *fn ,
		void *privdata )
{
	dictht *t0,*t1;
	const dictEntry *de;
	unsigned long m0,m1;
	if (dictSize(d) == 0)
	{
		return 0;
	}
	if (!dictIsRehashing(d) )
	{
		t0 = &( d->ht[0] );
		m0 = t0->sizemask;
		/* Emit entries at cursor */
		de = t0->table[v & m0];
		while (de)
		{
			fn( privdata , de );
			de = de->next;
		}
	}
	else
	{
		t0 = &d->ht[0];
		t1 = &d->ht[1];
		/* Make sure t0 is the smaller and t1 is the bigger table */
		if (t0->size > t1->size)
		{
			t0 = &d->ht[1];
			t1 = &d->ht[0];
		}
		m0 = t0->sizemask;
		m1 = t1->sizemask;
		/* Emit entries at cursor */
		de = t0->table[v & m0];
		while (de)
		{
			fn( privdata , de );
			de = de->next;
		}
		/* Iterate over indices in larger table that are the expansion
		 * of the index pointed to by the cursor in the smaller table */
		do
		{
			/* Emit entries at cursor */
			de = t1->table[v & m1];
			while (de)
			{
				fn( privdata , de );
				de = de->next;
			}
			/* Increment bits not covered by the smaller mask */
			v = ( ( ( v | m0 ) + 1 ) & ~m0 ) | ( v & m0 );
			/* Continue while bits covered by mask difference is non-zero */
		}
		while (v & ( m0 ^ m1 ));
	}
	/* Set unmasked bits so incrementing the reversed cursor
	 * operates on the masked bits of the smaller table */
	v |= ~m0;
	/* Increment the reverse cursor */
	v = rev( v );
	v++;
	v = rev( v );
	return v;
}

/* ------------------------- private functions ------------------------------ */

/* Expand the hash table if needed */
static int _dictExpandIfNeeded( dict *d )
{
	/* Incremental rehashing already in progress. Return. */
	if (dictIsRehashing(d) )
	{
		return DICT_OK;
	}
	/* If the hash table is empty expand it to the initial size. */
	if (d->ht[0].size == 0)
	{
		return dictExpand( d , DICT_HT_INITIAL_SIZE );
	}
	/* If we reached the 1:1 ratio, and we are allowed to resize the hash
	 * table (global setting) or we should avoid it but the ratio between
	 * elements/buckets is over the "safe" threshold, we resize doubling
	 * the number of buckets. */
	if (d->ht[0].used >= d->ht[0].size &&
			( dict_can_resize ||
					d->ht[0].used / d->ht[0].size > dict_force_resize_ratio ))
	{
		return dictExpand( d , d->ht[0].used * 2 );
	}
	return DICT_OK;
}

/* Our hash table capability is a power of two */
static unsigned long _dictNextPower( unsigned long size )
{
	unsigned long i = DICT_HT_INITIAL_SIZE;
	if (size >= LONG_MAX)
	{
		return LONG_MAX;
	}
	while (1)
	{
		if (i >= size)
		{
			return i;
		}
		i *= 2;
	}
}

/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned.
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. */
static int _dictKeyIndex( dict *d , const void *key )
{
	unsigned int h,idx,table;
	dictEntry *he;
	/* Expand the hash table if needed */
	if (_dictExpandIfNeeded( d ) == DICT_ERR)
	{
		return -1;
	}
	/* Compute the key hash value */
	h = dictHashKey(d, key);
	for (table = 0; table <= 1; table++)
	{
		idx = h & d->ht[table].sizemask;
		/* Search if this slot does not already contain the given key */
		he = d->ht[table].table[idx];
		while (he)
		{
			if (dictCompareKeys(d, key, he->key) )
					{
				return -1;
			}
			he = he->next;
		}
		if (!dictIsRehashing(d) )
		{
			break;
		}
	}
	return idx;
}

void dictEmpty( dict *d , void (callback)( void* ) )
{
	_dictClear( d , &d->ht[0] , callback );
	_dictClear( d , &d->ht[1] , callback );
	d->rehashidx = -1;
	d->iterators = 0;
}

void dictEnableResize( void )
{
	dict_can_resize = 1;
}

void dictDisableResize( void )
{
	dict_can_resize = 0;
}

#if 0

/* The following is code that we don't use for Redis currently, but that is part
 of the library. */

/* ----------------------- Debugging ------------------------*/

#define DICT_STATS_VECTLEN 50
static void _dictPrintStatsHt(dictht *ht)
{	
	unsigned long i, slots = 0, chainlen, maxchainlen = 0;
	unsigned long totchainlen = 0;
	unsigned long clvector[DICT_STATS_VECTLEN];
	if (ht->used == 0)
	{	
		printf("No stats available for empty dictionaries\n");
		return;
	}
	for (i = 0; i < DICT_STATS_VECTLEN; i++)
	{	
		clvector[i] = 0;
	}
	for (i = 0; i < ht->size; i++)
	{	
		dictEntry *he;
		if (ht->table[i] == NULL)
		{	
			clvector[0]++;
			continue;
		}
		slots++;
		/* For each hash entry on this slot... */
		chainlen = 0;
		he = ht->table[i];
		while(he)
		{	
			chainlen++;
			he = he->next;
		}
		clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;
		if (chainlen > maxchainlen)
		{	
			maxchainlen = chainlen;
		}
		totchainlen += chainlen;
	}
	printf("Hash table stats:\n");
	printf(" table size: %ld\n", ht->size);
	printf(" number of elements: %ld\n", ht->used);
	printf(" different slots: %ld\n", slots);
	printf(" max chain length: %ld\n", maxchainlen);
	printf(" avg chain length (counted): %.02f\n", (float)totchainlen/slots);
	printf(" avg chain length (computed): %.02f\n", (float)ht->used/slots);
	printf(" Chain length distribution:\n");
	for (i = 0; i < DICT_STATS_VECTLEN-1; i++)
	{	
		if (clvector[i] == 0)
		{	
			continue;
		}
		printf("   %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"", i, clvector[i], ((float)clvector[i]/ht->size)*100);
	}
}

void dictPrintStats(dict *d)
{	
	_dictPrintStatsHt(&d->ht[0]);
	if (dictIsRehashing(d))
	{	
		printf("-- Rehashing into ht[1]:\n");
		_dictPrintStatsHt(&d->ht[1]);
	}
}

/* ----------------------- StringCopy Hash Table Type ------------------------*/

static unsigned int _dictStringCopyHTHashFunction(const void *key)
{	
	return dictGenHashFunction(key, strlen(key));
}

static void *_dictStringDup(void *privdata, const void *key)
{	
	int len = strlen(key);
	char *copy = zmalloc(len+1);
	DICT_NOTUSED(privdata);
	memcpy(copy, key, len);
	copy[len] = '\0';
	return copy;
}

static int _dictStringCopyHTKeyCompare(void *privdata, const void *key1,
		const void *key2)
{	
	DICT_NOTUSED(privdata);
	return strcmp(key1, key2) == 0;
}

static void _dictStringDestructor(void *privdata, void *key)
{	
	DICT_NOTUSED(privdata);
	zfree(key);
}

dictType dictTypeHeapStringCopyKey =
{	
	_dictStringCopyHTHashFunction, /* hash function */
	_dictStringDup, /* key dup */
	NULL, /* val dup */
	_dictStringCopyHTKeyCompare, /* key compare */
	_dictStringDestructor, /* key destructor */
	NULL /* val destructor */
};

/* This is like StringCopy but does not auto-duplicate the key.
 * It's used for intepreter's shared strings. */
dictType dictTypeHeapStrings =
{	
	_dictStringCopyHTHashFunction, /* hash function */
	NULL, /* key dup */
	NULL, /* val dup */
	_dictStringCopyHTKeyCompare, /* key compare */
	_dictStringDestructor, /* key destructor */
	NULL /* val destructor */
};

/* This is like StringCopy but also automatically handle dynamic
 * allocated C strings as values. */
dictType dictTypeHeapStringCopyKeyValue =
{	
	_dictStringCopyHTHashFunction, /* hash function */
	_dictStringDup, /* key dup */
	_dictStringDup, /* val dup */
	_dictStringCopyHTKeyCompare, /* key compare */
	_dictStringDestructor, /* key destructor */
	_dictStringDestructor, /* val destructor */
};
#endif

